package levelTraversal;


import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public static void main(String[] args) {
        TreeNode A = new TreeNode(1);
        TreeNode B = new TreeNode(2);
        TreeNode C = new TreeNode(3);
        TreeNode D = new TreeNode(4);
        TreeNode E = new TreeNode(5);
        TreeNode F = new TreeNode(6);
        TreeNode G = new TreeNode(7);

        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;

        Solution solution = new Solution();
        solution.levelOrder1(A);
    }
}

class Solution {

    //两棵树的最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root ==null){
            return null;
        }
        if (root == p || root == q) {
            return root;
        }

        TreeNode ret1 = lowestCommonAncestor(root.left, p, q);
        TreeNode ret2 = lowestCommonAncestor(root.right, p, q);

        if (ret1 != null && ret2 != null) {
            return root;
        } else if (ret1 == null) {
            return ret2;
        }else return ret1;
    }


    //完全二叉树的检验
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (cur != null) {
                queue.offer(cur.left);
                queue.offer(cur.right);
            } else break;
        }

        //cur == null

        //对队列进行检查，如果队列全部为空，返回true，否则返回false
        int size = queue.size();
        while (size != 0) {
            if (queue.poll() != null) {
                return false;
            }
            size--;
        }
        return true;
    }


    //返回一个二维数组，存放每一层的节点
    public List<List<Integer>> levelOrder3(TreeNode root) {
        List<List<Integer>> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        TreeNode cur = null;   //更新队列变量
        Queue<TreeNode> queue = new LinkedList<>();  //创建一个存放层序遍历的队列

        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            int size = queue.size();


            while (size != 0) {
                cur = queue.poll();
//                System.out.println(cur.val);
                tmp.add(cur.val);
                size--;

                if (cur.left != null) {
                    queue.offer(cur.left);
                }

                if (cur.right != null) {
                    queue.offer(cur.right);
                }
            }
            list.add(tmp);
        }
        return list;
    }

    public void levelOrder1(TreeNode root) {
        if (root == null) {
            return;
        }

        Queue<TreeNode> queue = new LinkedList<>();  //创建一个存放层序遍历的队列

        TreeNode cur;   //更新队列变量

        queue.offer(root);
        while (!queue.isEmpty()) {
            cur = queue.poll();
            System.out.println(cur.val);

            if (cur.left != null) {
                queue.offer(cur.left);
            }

            if (cur.right != null) {
                queue.offer(cur.right);
            }
        }
    }


    //二叉树的层序遍历：使用队列辅助实现

}
